package com.example.lettcode._202411._20241118;

import java.util.*;

/*
448. 找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：
输入：nums = [1,1]
输出：[2]

提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
排序算O(n)
 */
public class _02_shu_zu_zhong_xiao_shi_de_shu_zi {
    public static void main(String[] args) {
        int[] nums = {4,3,2,7,6,2,3,1};
        List<Integer> disappearedNumbers = findDisappearedNumbers3(nums);
        disappearedNumbers.stream().forEach(System.out::println);
    }

    /*
        超时
     */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>(100000);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            list.add(nums[i]);
        }
        List<Integer> retList = new ArrayList<>(100000);
        for (int i = 1; i <= n; i++) {
            if (!list.contains(i)) {
                retList.add(i);
            }
        }
        return retList;
    }

    public static List<Integer> findDisappearedNumbers3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }

        List<Integer> retList = new ArrayList<>(100000);
        for (int i = 1; i <= n; i++) {
            if (set.add(i)) {
                retList.add(i);
            }
        }
        return retList;
    }


    /*
        给每个下标对应的值都+一个n，遍历数组，值小于n的，则都是未出现过的

        （所有的数 - 1 ） % n 后，都对应了nums的一个下标，并且这个下标，就是对应的[1 - n]以内的数字，
        将数组内的值，转化为了下标进行展现。
        例如：
        nums[0] = 4 -> nums[3] += n
        4在[1,n]是4， 在下标中[0, n-1]是3，所以，当nums[x] <= n时，则代表x+1是没有出现过的

     */
    public static List<Integer> findDisappearedNumbers2(int[] nums) {
       int n = nums.length;
        for (int num : nums) {
            int index = (num - 1) % n;
            nums[index] += n;
        }

        List<Integer> retList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                retList.add(i+1);
            }
        }
        return retList;
    }
}

